package leetcode.cn;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @version 1.8
 * @Author Djx_hmbb
 * @Date 2023/11/2 22:39
 * @注释:力扣15.三数之和
 */
public class TheNumOfThreeNum {
    //给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请
    //你返回所有和为 0 且不重复的三元组。
    //注意：答案中不可以包含重复的三元组。

    //示例 1：
    //输入：nums = [-1,0,1,2,-1,-4]
    //输出：[[-1,-1,2],[-1,0,1]]
    //解释：
    //nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
    //nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
    //nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
    //不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
    //注意，输出的顺序和三元组的顺序并不重要。

    //示例 2：
    //输入：nums = [0,1,1]
    //输出：[]
    //解释：唯一可能的三元组和不为 0

    //示例 3：
    //输入：nums = [0,0,0]
    //输出：[[0,0,0]]
    //解释：唯一可能的三元组和为 0 。


    //法一：不行!!!会漏掉数组情况
    public static List<List<Integer>> test(int[] nums) {
        List<List<Integer>> lists = new ArrayList<>();
        //先给nums排序
        Arrays.sort(nums);
        //再利用双指针找出sum=0 的三个数组，存入lists中。
        int left = 0, right = nums.length - 1, mid = right - 1;
        int sum = 0;
        while (left < right - 1 && mid > left) {
            if(nums[left]>0)break;
            sum = nums[left] + nums[right];
            if (nums[mid] > -sum) mid--;
            else if (nums[mid] < -sum)left++;
            else {
                //存入List
                lists.add(new ArrayList<Integer>(Arrays.asList(nums[left],nums[right],nums[mid])));
                if(nums[left]+nums[left+1]+nums[right]<0)left++;
                else right--;
                mid = right - 1;
            }
        }
        // 如果没有就返回空集。
        return lists;
    }

    //法二：用的是while循环
    public static List<List<Integer>> threeSum2(int[] nums) {
        List<List<Integer>> list = new ArrayList<>();
        //先给nums排序
        Arrays.sort(nums);
        int a = 0, left = a + 1, right = nums.length - 1;
        int sum = 0;
        //如果数组全是相同的，返回空
        //若为0，则返回三个0
/*        if (nums[0] == nums[nums.length - 1] && nums[0] == 0) {
            //返回
            list.add(new ArrayList<Integer>(Arrays.asList(0, 0, 0)));
            return list;
        }*/
        //在后面的区间里进行循环
        while (nums[a] <= 0 && a < nums.length - 2) {
            while (left < right) {
                sum = nums[left] + nums[right];
                if (sum == nums[a] * (-1)) {
                    //存入
                    list.add(new ArrayList<Integer>(Arrays.asList(nums[a], nums[left], nums[right])));
                    right--;
                    left++;
                    if (nums[left - 1] == nums[left]) left++;
                    if (nums[right + 1] == nums[right]) right--;
                } else if (sum < nums[a] * (-1)) {
                    left++;
                    if (nums[left - 1] == nums[left]) left++;
                } else {
                    right--;
                    if (nums[right + 1] == nums[right]) right--;
                }
            }
            a++;
            //判断a在数列中是否重复，重复则找到最后一个数字
            while (nums[a] == nums[a - 1]) a++;
            //left和right都要充值
            left = a + 1;
            right = nums.length - 1;
        }
        // 如果没有就返回空集。
        return list;
    }

    //法三：--最优（老师的解法） 用的是for循环
    public static List<List<Integer>> threeSum(int[] nums) {
        //1. 排序
        Arrays.sort(nums);
        //创建一个二位数组
        List<List<Integer>> lists = new ArrayList<>();
        int n = nums.length;
        //2. 利用双指针算法
        for (int i = 0; i < n; ) {//相当于a
            if (nums[i] > 0) break;
            int left = i + 1, right = n - 1, tar = -nums[i];
            while (left < right) {
                int sum = nums[left] + nums[right];
                if (tar > sum) left++;
                else if (tar < sum) right--;
                else {
                    lists.add(new ArrayList<Integer>(Arrays.asList(nums[i], nums[left], nums[right])));
                    right--;
                    left++;
                    //3. 去重
                    // 将移动后数字与移动前数字进行比较
                    while (left < right && nums[left] == nums[left - 1]) left++;
                    while (right < n - 1 && left < right && nums[right] == nums[right + 1]) right--;
                }
            }
            i++;
            //4. 去重
            while (i < n && nums[i] == nums[i - 1]) i++;
        }
        return lists;
    }

    public static void main(String[] args) {
        int[] nums = {-1, 0, 1, 2, -1, -4, -2, -3, 3, 0, 4};
        List<List<Integer>> lists = threeSum(nums);
        for (List<Integer> i :
               lists ) {
            System.out.println(i);
        }
        // test(nums);
//        List<List<Integer>> lll = threeSum(nums);
    }
}
